Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm

摘要

We propose Rademacher complexity bounds for multiclass classifiers trainedwith a two-step semi-supervised model. In the first step, the algorithmpartitions the partially labeled data and then identifies dense clusterscontaining $\kappa$ predominant classes using the labeled training examplessuch that the proportion of their non-predominant classes is below a fixedthreshold. In the second step, a classifier is trained by minimizing a marginempirical loss over the labeled training set and a penalization term measuringthe disability of the learner to predict the $\kappa$ predominant classes ofthe identified clusters. The resulting data-dependent generalization errorbound involves the margin distribution of the classifier, the stability of theclustering technique used in the first step and Rademacher complexity termscorresponding to partially labeled training data. Our theoretical resultexhibit convergence rates extending those proposed in the literature for thebinary case, and experimental results on different multiclass classificationproblems show empirical evidence that supports the theory.